1. Field of the Invention
The present invention relates generally to constrained multipath routing methods, and more particularly to a constrained multipath routing method, which finds multiple paths for satisfying the policy of restrictive conditions such as required amounts of traffic between routers, a set maximum hop count and specific node/link inclusion/exclusion conditions, accompanied when paths are routed in a multi-protocol label switching network, and an optimal divided amount of traffic for each path, and a computer-readable recording medium, which stores a program for performing the routing method.
2. Description of the Prior Art
Recently, as both the number of Internet users and demands for multimedia services have increased, demands for large capacity communication services enabling the transfer of more Internet traffic are gradually increased. In addition, Broadband Integrated Services Digital Networks (B-ISDN) have rapidly been developed so as to meet requests for a variety of services including electronic mail services, electronic commerce, moving picture services like Internet broadcast, remote video conferencing, home shopping, online real time games and home networking using the Internet.
In a conventional backbone network, a traffic engineering method is performed by just bypassing the traffic at a bottleneck point using a single path. Currently, Internet routers mostly transmit traffic on the basis of a single shortest path routing method, and partially use a number of shortest paths having the same cost, that is, an equal cost multipath. However, because the Internet using Multiprotocol Label Switching (MPLS) technology that is recently developed and utilized can support routing using another paths in addition to the shortest path, it can complement the disadvantages of the conventional traffic engineering method. Such MPLS is a transfer mechanism designed to provide flowability and expandability of the Internet Protocol (IP) while providing a quality of service (QoS) equal to Asynchronous Transfer Mode (ATM) or Frame Relay technology. MPLS can provide improved IP services such as a virtual private network (VPN) or traffic engineering, which has recently become a hot issue in the Internet and can be provided by IP network.
As described above, if the traffic engineering method is performed using a multipath routing mechanism, the maximization of the network efficiency and the optimization of the resource utilization can be realized. In order to perform this, each path of traffic must be calculated in consideration of a required amount of traffic between routers, a maximum hop count of set path and specific node/link inclusion/exclusion conditions together with each other, and further the amount of traffic to be included in each calculated path must be calculated.
In fact, with regard to a backbone network supervisor, it is a significant matter to set a path so as to minimize the maximum value of the degree of utilization of each link in the network and the degree of resource utilization of the entire network when traffic requirements between routers are given. When a bottleneck point continuing for a long time is generated in the Internet, the conventional Internet traffic engineering method solves the problem by expanding the capacities of switch/router and a link as a solution of physical/link layers. As another solution, a method for setting a new path not passing through the bottleneck point by varying a metric assigned to the interface of the router is used as a solution of a third layer, thus allowing the confusion occurring at a specific bottleneck point to be solved.
However, such conventional technologies are problematic in that it takes too much time to adapt the solutions to the network from a time point of the derivation of the solutions, costs are increased, and the bottleneck of the network is just moved to another point rather than basically solved.
In the prior art, a first thesis entitled “Explicit routing algorithms for Internet traffic engineering” in 1999 discloses an explicit routing algorithm for Internet traffic engineering so as to solve a traffic engineering problem capable of calculating multiple paths and a traffic division ratio of each path to minimize a maximum link utilization, by a linear programming. The first thesis is designed as a routing algorithm to minimize a maximum link utilization in the MPLS network. Here, in the multipath routing algorithm of the first thesis, after the degree of maximum link utilization is minimized by performing a modeling method using a linear programming, the multipath corresponding to each traffic requirement and sequential traffic division ratio of each path are obtained. However, such method is disadvantageous in that it only considers the maximum link utilization as the basis of the optimization process, but excludes the optimization basis for minimizing the degree of resource utilization, such that the hop count is increased when the path is routed, thus preventing the routing algorithm from displaying optimal efficiency.
A second thesis entitled “Analytical framework for dynamic traffic partitioning in MPLS networks” in 2000 discloses a method for calculating a traffic division ratio on multiple paths, which can minimize delay or packet loss rate in the MPLS network which is capable of satisfying the quality of services (QoS). The method divides traffic on multiple paths by calculating optimal traffic division ratios in consideration of a minimum delay time or a packet loss rate in the multiple paths preset by a routing protocol. However, in the second thesis, the traffic division ratio is calculated by only considering the minimum delay time or the packet loss rate as the basis for optimization, without considering the maximum link utilization and minimum resource utilization, such that the bottleneck of the network cannot be basically solved, and in particular there is an overhead that the traffic division ratio must be always calculated with respect to only a single traffic requirement.
Further, in the U.S. Pat. No. 5,727,051, a method and system for deciding a virtual path capacity so as to make blocking probabilities of all physical links in the ATM network as uniform as possible is disclosed. However, the method and the system is problematic in that it considers only a single path, thus it can be adapted only to a network in which the traffic flowing into the network follows an Erlang distribution. Moreover the method decides the capacity without reflecting restrictive conditions included in the virtual paths, thereby preventing the method and the system from fulfilling requests for high speed communication service.